// =====================================================================================
//
//       Filename:  bst.cpp
//
//    Description:  Implémentation d'une structure d'arbre binaire automatiquement équilibré,
//					de type AVL-Tree (Adelson-Velskii et Landis, 1962)
//
//        Version:  1.0
//        Created:  17/08/2009 10:50:00
//       Revision:  none
//       Compiler:  g++
//
//         Author:  François Hissel (fh), francois.hissel@m4x.org
//        Company:
//
// =====================================================================================

#include	"bst.h"

/***********************************/
/* IMPLEMENTATION DE LA CLASSE BST */
/***********************************/
template<class T,int (*compare)(void *a,void *b)>
void Bst<T,compare>::insert(const T &element) {
	if (root==0) {
		root=new BstNode<T,compare>(element,0,0,0);
		root->_depth=0;
		return;
	}
	BstNode<T,compare> *node=root;
	bool stop=false;
	int comp;
	do {
		comp=compare(&element,&(node->data));
		if (comp<=0) {
			if (node->left) node=node->left; else stop=true;
		} else {
			if (node->right) node=node->right; else stop=true;
		}
	} while (!stop);
	//A ce stade, node contient la feuille de l'arbre où s'est terminée la recherche
	BstNode<T,compare> *newnode=new BstNode(element,0,0,node);
	if (comp<=0) {	// On insère le noeud du côté droit ou gauche de la feuille selon sa valeur
		node->left=newnode;
	} else {
		node->right=newnode;
	}
	//On remonte au premier parent pour lequel le sous-arbre est déséquilibré
}

/***************************************/
/* IMPLEMENTATION DE LA CLASSE BSTNODE */
/***************************************/
template<class T,int (*compare)(void *a,void *b)>
int BstNode<T,compare>::depth() {
	if (_depth<0) {
		double dl=(left)?left->depth()+1:0;
		double dr=(right)?right->depth()+1:0;
		if (dl>dr) _depth=dl; else _depth=dr;
	}
	return _depth;
}

template<class T,int (*compare)(void *a,void *b)>
BstNode<T,compare>::~BstNode() {
	delete left;
	delete right;
}

template<class T,int (*compare)(void *a,void *b)>
bool BstNode<T,compare>::search(const T &source,const BstNode<T,compare> *const &element) const {
	int comp=compare(&data,&source);
	if (comp==0) {
		element=this;
		return true;
	}
	if (comp<0) {
		if (right) return right->search(source,element);
	} else {
		if (left) return left->search(source,element);
	}
	element=this;
	return false;
}
